//力扣2. 两数相加
import java.util.*;
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        List<Integer> list = new ArrayList<>();
        boolean flag = false;
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        while(cur1!=null&&cur2!=null){
            int remainder = 0;
            if(flag){
                remainder++;
                flag=false;
            }
            remainder+=(cur1.val+cur2.val);
            list.add(remainder%10);
            if(remainder/10==1){
                flag=true;
            }
            cur1=cur1.next;
            cur2=cur2.next;
        }
        while(cur1!=null){
            int remainder = 0;
            if(flag){
                remainder++;
                flag=false;
            }
            remainder+=cur1.val;
            list.add(remainder%10);
            if(remainder/10==1){
                flag=true;
            }
            cur1=cur1.next;
        }
        while(cur2!=null){
            int remainder = 0;
            if(flag){
                remainder++;
                flag=false;
            }
            remainder+=cur2.val;
            list.add(remainder%10);
            if(remainder/10==1){
                flag=true;
            }
            cur2=cur2.next;
        }
        if(flag){
            list.add(1);
        }
        ListNode newH = new ListNode();
        cur1 = newH;
        for(int i=0;i<list.size();i++){
            ListNode newN = new ListNode(list.get(i));
            cur1.next=newN;
            cur1 = cur1.next;
        }
        return newH.next;
    }
}


//更简洁的代码
class Solution1 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        List<Integer> list = new ArrayList<>();
        int carry = 0;  // 使用int代替boolean，可以处理多级进位

        ListNode cur1 = l1;
        ListNode cur2 = l2;

        while(cur1 != null || cur2 != null) {
            int sum = carry;
            if(cur1 != null) {
                sum += cur1.val;
                cur1 = cur1.next;
            }
            if(cur2 != null) {
                sum += cur2.val;
                cur2 = cur2.next;
            }

            list.add(sum % 10);
            carry = sum / 10;
        }

        if(carry > 0) {
            list.add(carry);
        }

        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for(int num : list) {
            current.next = new ListNode(num);
            current = current.next;
        }

        return dummy.next;
    }
}



//19. 删除链表的倒数第 N 个结点
class Solution10 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int len = 0;
        ListNode cur = head;
        while(cur!=null){
            len++;
            cur=cur.next;
        }
        if(len==n){
            return head.next;
        }
        len-=n;
        cur = head;
        while(cur!=null){
            len--;
            if(len==0){
                cur.next=cur.next.next;
            }else{
                cur=cur.next;
            }
        }
        return head;
    }
}